// #include <iostream>
// #include <vector>
// #include <algorithm>

// using namespace std;

// //求自顶到底部的最小路径和
// int main()
// {
//     vector<int> v1 = {2};
//     vector<int> v2 = {3,4};
//     vector<int> v3 = {6,5,7};
//     vector<int> v4 = {4,1,8,3};
//     vector<vector<int>> vec;
//     vec.push_back(v1);
//     vec.push_back(v2);
//     vec.push_back(v3);
//     vec.push_back(v4);

//     vector<vector<int>> dp(vec.size(),vector<int>(v4.size(),0));

//     for(int i = 0;i < v4.size();i++)
//     {
//         dp[vec.size() - 1][i] = v4[i];
//     }

//     for(int i = vec.size() - 2;i >= 0;i--)
//     {
//         for(int j = 0;j < v4.size();j++)
//         {
//             dp[i][j] = vec[i][j] + std::min(dp[i + 1][j],dp[i + 1][j + 1]);
//         }
//     }

//     for(auto v : dp)
//     {
//         for(auto i : v)
//         {
//             cout << i << " ";
//         }
//         cout << endl;
//     }
// }

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        for (int i = n - 2; i >= 0; --i) {  // 从倒数第二行开始
            for (int j = 0; j <= i; ++j) {
                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }
        return triangle[0][0];  // 最终结果在顶点
    }
};

int main() {
    vector<vector<int>> triangle = {
        {2},
        {3, 4},
        {6, 5, 7},
        {4, 1, 8, 3}
    };
    Solution sol;
    cout << sol.minimumTotal(triangle) << endl;  // 输出 11
}
